CODE 37. Unique Binary Search Trees II

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/21/2013-09-21-CODE 37 Unique Binary Search Trees II/

访问原文「CODE 37. Unique Binary Search Trees II」

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

public ArrayList<TreeNode> generateTrees(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (n <= 0) {
		ArrayList<TreeNode> node = new ArrayList<TreeNode>();
		node.add(null);
		return node;
	}
	return dfs(1, n);
}

ArrayList<TreeNode> dfs(int start, int end) {
	if (end - start < 0) {
		return null;
	} else if (end - start == 0) {
		ArrayList<TreeNode> node = new ArrayList<TreeNode>();
		node.add(new TreeNode(start));
		return node;
	}
	ArrayList<TreeNode> node = new ArrayList<TreeNode>();
	for (int i = start; i <= end; i++) {
		ArrayList<TreeNode> leftNodes = dfs(start, i - 1);
		ArrayList<TreeNode> rightNodes = dfs(i + 1, end);
		if (null != leftNodes || null != rightNodes) {
			if (null == leftNodes) {
				for (TreeNode rightNode : rightNodes) {
					TreeNode newNode = new TreeNode(i);
					newNode.right = rightNode;
					node.add(newNode);
				}
			} else if (null == rightNodes) {
				for (TreeNode leftNode : leftNodes) {
					TreeNode newNode = new TreeNode(i);
					newNode.left = leftNode;
					node.add(newNode);
				}
			} else {
				for (TreeNode leftNode : leftNodes) {
					for (TreeNode rightNode : rightNodes) {
						TreeNode newNode = new TreeNode(i);
						newNode.left = leftNode;
						newNode.right = rightNode;
						node.add(newNode);
					}
				}
			}
		} else {
			TreeNode newNode = new TreeNode(i);
			node.add(newNode);
		}

	}
	return node;
}